//
//  LinkedList.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

///        prev _________    next    _________   next    _______    next   _______    next   __________     next
///  nil <------| 头结点 |  --------> | 首节点 | --------> | 其他 | --------> | 末节点| -------> |  尾节点  |  ------->  nil
///             | header|  <-------- | first | <-------- | 节点 | <-------  | last | <------  | trailer |
///             ---------    prev    --------    prev    -------    prev   --------   prev   ------------
public final  class LinkedList<Element> {
    
    var _size: Int
    
    /// 哨兵节点
    let _header: LinkedListNode<Element>
    let _trailer: LinkedListNode<Element>
    
    public var isEmpty: Bool { return _size == 0 }
    public var count: Int { return _size }

    
    public var first: LinkedListNode<Element>? {
        get {
            if isEmpty { return nil }
            return _header.successor
        }
    }
    
    public var last: LinkedListNode<Element>? {
        get {
            if isEmpty { return nil }
            return _trailer.predecessor
        }
    }
    
    /// 初始化一个空链表
    public init() {
        _size = 0
        _header = LinkedListNode()
        _trailer = LinkedListNode()
        _header.successor = _trailer
        _trailer.predecessor = _header
    }
    
    /// 通过其他链表初始化
    public convenience init(_ other: LinkedList<Element>) {
        self.init()
        var nd = other.first
        while let next = nd, next !== other._trailer {
            // _size由insert隐式递增
            insertAsLast(next.value!)
            nd = next.successor
        }
    }
    
    deinit { debugPrint(String(format: "\(self) = %p is deinitializing", UInt(bitPattern: ObjectIdentifier(self)))) }
}

extension LinkedList: CustomStringConvertible {
    public var description: String {
        var s = "["
        var node = _header.successor
        while let nd = node, nd !== _trailer {
            s += "\(String(describing: nd.value))"
            node = nd.successor
            if node != nil { s += ", " }
        }
        return s + "]"
    }
}

extension LinkedList: ExpressibleByArrayLiteral {
    public convenience init(arrayLiteral elements: Element...) {
        self.init()
        elements.forEach { insertAsLast($0) }
    }
}
